package com.xiyou.week05.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56. 合并区间
 *
 * @ClassName：Merge
 * @Author：西柚
 * @Date：2022/2/8 2:16 下午
 * @Versiion：1.0
 */
public class Merge {

    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     * <p>
     * 示例 1：
     * <p>
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        int farthest = -1;
        int start = -1;
        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            if (left <= farthest) {
                farthest = Math.max(farthest, right);
            } else {
                if (farthest != -1) {
                    ans.add(new int[]{start, farthest});
                }
                start = left;
                farthest = right;
            }
        }
        ans.add(new int[]{start, farthest});
        return ans.toArray(new int[ans.size()][2]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        Merge merge = new Merge();
        System.out.println(Arrays.toString(merge.merge(intervals)));
    }
}
